/**
 * The MIT License (MIT)
 *
 * Copyright (c) 2013 Armin Lunkeit, Fabian Poehland, Leonard Scharff
 *
 *
 * Permission is hereby granted, free of charge, to any person obtaining _a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:

 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
package tub.adm1;

import java.util.LinkedList;
import java.util.List;

/**
 * 
 * @author a.lunkeit - alunkeit(at)gmail(dot)com
 *
 *
 */
public class EdmondsKarp
{
  /**
   * The network initialized by reading the CAT file
   */
  Graph _network;

  /**
   * The residual graph is used for the implementation of the augmenting path algorithm
   */
  Graph _residualGraph;
  
  /**
   * Stores the operation result
   */
  float _maxFlow = 0;

  public EdmondsKarp( Graph g )
  {
    _network = g;

    initResidual();
  }

  /**
   * Starts execution of the Edmonds-Karp algorithm
   * 
   * http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
   * 
   * algorithm EdmondsKarp
   * input:
   *     C[1..n, 1..n] (Capacity matrix)
   *     E[1..n, 1..?] (Neighbour lists)
   *     s             (Source)
   *     t             (Sink)
   * output:
   *     f             (Value of maximum flow)
   *     F             (A matrix giving a legal flow with the maximum value)
   * f := 0 (Initial flow is zero)
   * F := array(1..n, 1..n) (Residual capacity from u to v is C[u,v] - F[u,v])
   * forever
   *     m, P := BreadthFirstSearch(C, E, s, t, F)
   *     if m = 0
   *         break
   *     f := f + m
   *     (Backtrack search, and write flow)
   *     v := t
   *     while v ≠ s
   *         u := P[v]
   *         F[u,v] := F[u,v] + m
   *         F[v,u] := F[v,u] - m
   *         v := u
   * return (f, F)
   * 
   * @param s - The id of the source vertex in the CAT file. 
   * @param t - The id of the target vertex in the CAT file.
   * @return Float value of the flow
   */
  public float solve( int s, int t )
  {

    /*
     * At first try to find a path from s to t. If there exists no path a null
     * value is returned and the flow value will be 0
     */
    LinkedList<GoldbergTarjan.Edge> path = getBFSPath( s, t );
    
    /* 
     * while there is an augmenting path update the flow values on the path
     */
    while( path.isEmpty() == false )
    {
      float min = findMinFlowValue( path );
      
      updateFlowValues( path, min );
      path = getBFSPath( s, t );
    }
    
    /*
     * Sum up the flow values and returns the result
     */
    for( int counter = 0; counter < _network.deltaPlusIds( s ).size(); counter++ )
    {
      _maxFlow += _network.getEdge( s, _network.deltaPlusIds( s ).get( counter ))._fe;
    }
    
    return _maxFlow;
  }

  protected void updateFlowValues( LinkedList<GoldbergTarjan.Edge> path, float f )
  {
    for( int i = 0; i < path.size(); i++ )
    {
      GoldbergTarjan.Edge gij = path.get( i );
      GoldbergTarjan.Edge gji = null;
      int head = gij._headId;
      int tail = gij._tailId;

      float rij = gij._rij;
      float rji = -1;
      boolean inv = false;

      if( _residualGraph.getEdge( tail, head ) != null )
      {
        inv = true;
        gji = _residualGraph.getEdge( tail, head );
        rji = gij._weight;
      }

      GoldbergTarjan.Edge eij = _network.getEdge( head, tail );
      float cij = 0;
      float fij = 0;

      if( eij != null )
      {
        cij = eij._weight;
        fij = eij._fe;
      }

      GoldbergTarjan.Edge eji = _network.getEdge( tail, head );
      
      float fji = 0;

      if( eji != null )
        fji = eji._fe;

      if( eij != null && cij - fij >= f )
      {

        eij._fe = fij + f;
        gij._rij = rij - f;

        if( inv )
        {
          gji._rij = rji + f;
        }
        else
        {
          gij = new GoldbergTarjan.Edge();
          gij._headId = tail;
          gij._tailId = head;
          gij._rij = f;
          _residualGraph.addEdge( gij );

        }
      }
      else if( eji != null && f <= fji )
      {

        eji._fe = fji - f;
        gij._rij = rij - f;

        if( inv )
          gji._rij = rji + f;

        else
        {
          gij = new GoldbergTarjan.Edge();
          gij._headId = tail;
          gij._tailId = head;
          gij._rij = f;
        }

      }
      else
      {
        float a = cij - fij - f;

        if( null != eji )
          eji._fe = fji + a;
        
        eij._fe = cij;

        if( inv )
        {
          gji._rij = rji + a;
        }

        else
        {
          gji = new GoldbergTarjan.Edge();
          gji._headId = tail;
          gji._tailId = head;
          gji._rij = a;
          _residualGraph.addEdge( gji );
        }
      }

      if( f == rij )
      {
        _residualGraph.removeEdge( head, tail );
      }
    }
  }

  /**
   * Returns the minimum flow value on a given path.
   * @param path - s-t- Path containing of edges
   * @return Float value of minimum value
   */
  protected float findMinFlowValue( LinkedList<GoldbergTarjan.Edge> path )
  {
    float min = Integer.MAX_VALUE;

    for( int i = 0; i < path.size(); i++ )
    {
      float rij = path.get( i )._rij;

      if( rij < min )
      {
        min = rij;
      }
    }
    return min;
  }

  /**
   * Implements the breadth first search. 
   * 
   * http://en.wikipedia.org/wiki/Breadth-first_search
   * 
   * 1  procedure BFS(G,v) is
   * 2      create a queue Q
   * 3      create a set V
   * 4      enqueue v onto Q
   * 5      add v to V
   * 6      while Q is not empty loop
   * 7          t ← Q.dequeue()
   * 8          if t is what we are looking for then
   * 9              return t
   * 10         end if
   * 11         for all edges e in G.adjacentEdges(t) loop
   * 12             u ← G.adjacentVertex(t,e)
   * 13             if u is not in V then
   * 14                  add u to V
   * 15                  enqueue u onto Q
   * 16             end if
   * 17         end loop
   * 18     end loop
   * 19     return none
   * 20 end BFS
   * 
   * @param _network
   * @param start
   * @param target
   * @return
   */
  protected LinkedList<GoldbergTarjan.Edge> getBFSPath( int start, int target )
  {
    LinkedList<GoldbergTarjan.Edge> out = new LinkedList<GoldbergTarjan.Edge>();
    LinkedList<GoldbergTarjan.Vertex> queue = new LinkedList<GoldbergTarjan.Vertex>();

    _residualGraph.getVertex( start )._predecessor = 0;

    queue.add( _residualGraph.getVertex( start ));
    
    while( !queue.isEmpty() && !queue.getFirst().equals( _residualGraph.getVertex( target )))
    {
      GoldbergTarjan.Vertex curr = queue.getFirst();
      List<Integer> list = _residualGraph.deltaPlusIds( curr._id );

      for( int i = 0; i < list.size(); i++ )
      {
        GoldbergTarjan.Vertex p = _residualGraph.getVertex( list.get( i ) );

        if( p._predecessor == Integer.MAX_VALUE )
        { 
          p._predecessor = curr._id;
          queue.add( p ); 
        }
      }
      queue.remove();
    }

    if( queue.isEmpty())
    {
      return out;
    }
    else
    {
      GoldbergTarjan.Vertex curr = _residualGraph.getVertex( target );

      while( curr.equals( _residualGraph.getVertex( start ) ) == false )
      {
        int pred = curr._predecessor;

        GoldbergTarjan.Edge e = _residualGraph.getEdge( pred, curr._id );
        out.addFirst( e );
        curr = _residualGraph.getVertex( pred );
      }
    }
  
    for( int i = 1; i <= _residualGraph.vertexCnt(); i++ )
    {
      if( i != start )
        _residualGraph.getVertex( i )._predecessor = Integer.MAX_VALUE;
    }
    
    return out;
  }

  protected void initResidual()
  {
    _residualGraph = new Graph();

    List<GoldbergTarjan.Vertex> vl = _network.getVertices();
    List<GoldbergTarjan.Edge> el = _network.getEdges();

    for( int i = 0; i < vl.size(); i++ )
    {
      GoldbergTarjan.Vertex v = new GoldbergTarjan.Vertex();
      v._id = vl.get( i )._id;

      v._predecessor = Integer.MAX_VALUE;
      _residualGraph.addVertex( v );
    }

    for( int i = 0; i < el.size(); i++ )
    {
      GoldbergTarjan.Edge z = el.get( i );
      z._fe = 0;

      GoldbergTarjan.Edge e = new GoldbergTarjan.Edge();
      e._headId = z._headId;
      e._tailId = z._tailId;
      e._rij = z._weight;

      _residualGraph.addEdge( e );
    }
  }
}